package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/15 12:03
 * @description：https://leetcode-cn.com/problems/loud-and-rich/
 */
public class 喧闹和富有 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.loudAndRich(
                new int[][]{{1, 0}, {2, 1}, {3, 1}, {3, 7}, {4, 3}, {5, 3}, {6, 3}},
                new int[]{3, 2, 5, 4, 6, 1, 7, 0})));
    }

    class Solution {
        public int[] loudAndRich(int[][] richer, int[] quiet) {
            int len = quiet.length;
            // 存储有向图
            List<List<Integer>> edges = new ArrayList<>();
            // 存储每个节点的入度
            int[] inDeg = new int[len];
            // 存储quiet和person的对应关系
            Map<Integer, Integer> map = new HashMap<>();
            int[] ans = new int[len];
            for (int i = 0; i < len; i++) {
                edges.add(new ArrayList<>());
            }
            for (int i = 0; i < len; i++) {
                map.put(quiet[i], i);
            }
            for (int[] nums : richer) {
                edges.get(nums[0]).add(nums[1]);
                inDeg[nums[1]]++;
            }
            for (int i = 0; i < ans.length; i++) {
                ans[i] = quiet[i];
            }
            // 临时存储入度为0的节点
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < len; i++) {
                if (inDeg[i] == 0) {
                    queue.offer(i);
                }
            }
            while (!queue.isEmpty()) {
                Integer cur = queue.poll();
                // 获取当前节点的最优解
                int curQuiet = Math.min(ans[cur], quiet[cur]);
                ans[cur] = curQuiet;
                // 向下传递
                for (Integer in : edges.get(cur)) {
                    ans[in] = Math.min(ans[in], curQuiet);
                    if (--inDeg[in] == 0) {
                        queue.offer(in);
                    }
                }
            }
            // 根据quiet获取person
            for (int i = 0; i < ans.length; i++) {
                ans[i] = map.get(ans[i]);
            }
            return ans;
        }
    }

}
